module Queue.Deque (Queue,
                    isEmpty,
                    empty,
                    addEnd,
                    addFront,
                    last,
                    init,
                    head,
                    tail) where

import Prelude hiding (head, tail, last, init)

data Queue a = Queue{left::[a], lenLeft::Int, right::[a], lenRight::Int}

c :: Int
c = 2

isEmpty Queue{left=[]} = True
isEmpty _ = False

empty = Queue [] 0 [] 0

addEnd q@Queue{right=xs,lenRight=lr} x = norm q{right=x:xs,lenRight=lr+1}

addFront q@Queue{left=xs,lenLeft=ll} x = norm q{left=x:xs,lenLeft=ll+1}

head Queue{left=x:_} = x
head Queue{left=[], right=x:[]} = x
head _ = error "head on empty queue"

last Queue{right=x:_} = x
last Queue{right=[], left=x:[]} = x
last Queue{right=[]} = error "last on empty queue" 

tail q@Queue{left=_:xs,lenLeft=ll} = norm q{left=xs,lenLeft=ll-1}
tail q@Queue{left=[], right=_:xs, lenRight=lr} = norm q{right=xs,lenRight=lr-1}
tail _ = error "tail on empty queue"

init q@Queue{right=_:xs,lenRight=lr} = norm q{right=xs,lenRight=lr-1}
init q@Queue{right=[], left=_:xs, lenLeft=ll} = norm q{left=xs,lenLeft=ll-1}
init _ = error "init on empty queue"

-- Invariante:
-- length left <= c * length right + 1        links ist hoechstens c mal so lang wie rechts (+1)
-- UND 
-- length right <= c * length left + 1        rechts ist hoechstens c mal so lang wie links (+1)
--
-- Norm wird bei von allen modifizierenden Funktionen aufgerufen.
-- Norm selbst stellt die Invariante sicher, da sie im Falle einer Verletzung die Listen balanciert.
-- Nach dem Aufruf sind beide Listen entweder gleich lang, oder eine hat ein Element mehr.
-- Dadurch gillt die Invariante für alle c groesser 1.

norm q@Queue{left=xs,lenLeft=ll,right=ys,lenRight=lr} =
  if lr > c*ll+1 then
        let 
            splitIndex = (ll+lr) `div` 2
            (restingRightPart, movingPart) = splitAt splitIndex ys
        in
            Queue (xs++reverse movingPart) (ll+lr-splitIndex) restingRightPart splitIndex
  else
        if ll > c*lr+1 then
            let 
                splitIndex = (ll+lr) `div` 2
                (restingLeftPart, movingPart) = splitAt splitIndex xs
        in
                Queue restingLeftPart splitIndex (ys++reverse movingPart) (lr+ll-splitIndex)
        else q
        
instance Show a => Show (Queue a) where
        show = toString
        
toString :: Show a => Queue a -> String
toString Queue{right=r, left=l} = "(left: " ++ show l ++ "\n right:" ++ show r ++" )"
